//
//  15.swift
//  Swift-LeetCode
//
//  Created by 卢悦明 on 2024/3/14.
/*
 https://leetcode.cn/problems/3sum/description/
 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

 你返回所有和为 0 且不重复的三元组。

 注意：答案中不可以包含重复的三元组。

 示例 1：

 输入：nums = [-1,0,1,2,-1,-4]
 输出：[[-1,-1,2],[-1,0,1]]
 解释：
 nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
 nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
 nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
 不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
 注意，输出的顺序和三元组的顺序并不重要。
 示例 2：

 输入：nums = [0,1,1]
 输出：[]
 解释：唯一可能的三元组和不为 0 。
 示例 3：

 输入：nums = [0,0,0]
 输出：[[0,0,0]]
 解释：唯一可能的三元组和为 0
 */

import UIKit

class ThreeNumSum: NSObject {
    func QA() {
        print(threeSum([0, 0, 0]))
    }
    
    func threeSum(_ nums: [Int]) -> [[Int]] {
        if nums.count < 3 { return [] }
        var resultArray = [[Int]]()
        var nums = nums
        // 必须要排序
        nums.sort()
        
        var i = 0
        let count = nums.count
        while i < count - 2 {
            if i > 0 && nums[i] == nums[i-1] { // 去重
                i += 1
                continue
            }
            var l = i + 1
            var r = count - 1
            
            while l < r {
                let result = nums[i] + nums[l] + nums[r]
                if result == 0 {
                    let array = [nums[i], nums[l], nums[r]]
                    resultArray.append(array)
                    while l < r && nums[l] == nums [l + 1] { // 去重
                        l += 1
                    }
                    while l < r && nums[r] == nums [r - 1] { // 去重
                        r -= 1
                    }
                    r -= 1
                    l += 1
                } else if result < 0 {
                    l += 1
                } else {
                    r -= 1
                }
            }
            
            i += 1
        }
        
        return resultArray
    }
}
